package com.javabasic.algorithm.other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Objects;

/**
 * @Author xiongmin
 * @Description
 * @Date 2021/1/27 11:30
 * @Version 1.0
 * @TODO
 **/
public class MazeProblem2 {


    public static void main(String[] args) {
        ArrayList<Integer> raw1 = new ArrayList<>(Arrays.asList(0, 0, 0, 0, 0));
        ArrayList<Integer> raw2 = new ArrayList<>(Arrays.asList(0, 1, 0, 1, 0));
        ArrayList<Integer> raw3 = new ArrayList<>(Arrays.asList(0, 1, 0, 0, 0));
        ArrayList<Integer> raw4 = new ArrayList<>(Arrays.asList(1, 1, 1, 0, 0));
        ArrayList<Integer> raw5 = new ArrayList<>(Arrays.asList(0, 0, 0, 0, 0));
        ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>() {{
            add(raw1);
            add(raw2);
            add(raw3);
            add(raw4);
            add(raw5);
        }};


        getAllMinimumRaod(map);
    }

    public static void getAllMinimumRaod(ArrayList<ArrayList<Integer>> map) {
        int size = map.size();
        int[][] next = new int[][]{
                {-1, 0}, // 上 cost = 3
                {0, 1},  // 右 cost = 2
                {1, 0},  // 下 cost = 1
                {0, -1}  // 左 cost = 2
        };
        int nextLen = next.length;
        HashMap<Integer, Integer> costMap = new HashMap<>();
        costMap.put(0, 3);
        costMap.put(1, 2);
        costMap.put(2, 1);
        costMap.put(3, 2);
        boolean[][] visit = new boolean[size][size];


        int min = Integer.MAX_VALUE;
        LinkedList<Step> steps = new LinkedList<>();
        Step begin = new Step(0, 0, 0), temp;
        visit[0][0] = true;

        int endx = size - 1, endy = size - 1;
        steps.add(begin);

        // 记录结果的路径
        ArrayList<Step> result = new ArrayList<>();
        HashMap<Step, Step> parent = new HashMap<>();

        int tempx, tempy;
        while (!steps.isEmpty()) {
            temp = steps.poll();
            if (temp.cost > min) {
                continue;
            }
            // 找到目标节点
            if (temp.x == endx && temp.y == endy) {
                // 如果更小的花费路径，清空原来保存的路径
                if (temp.cost < min) {
                    result.clear();
                }
                min = temp.cost;
                // TODO 保存路径
                while (null != temp) {
                    result.add(temp);
                    // TODO 保存多条路径
                    temp = parent.getOrDefault(temp, null);
                    if (null == temp) {
                        break;
                    }
                }
                continue;
            }
            for (int i = 0; i < nextLen; i++) {
                tempx = temp.getX() + next[i][0];
                tempy = temp.getY() + next[i][1];
                if (check(tempx, tempy, size, map)) {
                    Step stepTemp = new Step(tempx, tempy, temp.getCost() + costMap.get(i));
                    if (visit[tempx][tempy] == false) {
                        visit[tempx][tempy] = true;
                        steps.offer(stepTemp);
                        // 只有进入队列的节点才去保存父节点
                        parent.put(stepTemp, temp);
                    } else {
                        if (steps.contains(stepTemp)) {
                            Iterator<Step> iterator = steps.iterator();
                            while (iterator.hasNext()) {
                                Step step = iterator.next();
                                if (step.equals(stepTemp)) {
                                    if (step.getCost() > stepTemp.getCost()) {
                                        iterator.remove();
                                        steps.offer(stepTemp);
                                        parent.put(stepTemp, temp);
                                    }
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }

        Collections.reverse(result);
        for (Step step : result) {
            System.out.print(step + "->");
        }


    }

    private static boolean check(int tempx, int tempy, int size, ArrayList<ArrayList<Integer>> map) {
        // 出界或者该坐标上为1，表示阻断均是不可行走的节点
        if (tempx < 0 || tempy < 0 || tempx >= size || tempy >= size || map.get(tempx).get(tempy) == 1) {
            return false;
        }
        return true;
    }

}

//class Step {
//    int x, y;
//    int cost;
//
//    public Step(int x, int y) {
//        this.x = x;
//        this.y = y;
//    }
//
//    public Step() {
//    }
//
//    public Step(int x, int y, int cost) {
//        this.x = x;
//        this.y = y;
//        this.cost = cost;
//    }
//
//    @Override
//    public boolean equals(Object o) {
//        if (this == o) return true;
//        if (o == null || getClass() != o.getClass()) return false;
//        Step step = (Step) o;
//        return x == step.x &&
//                y == step.y;
//    }
//
//    @Override
//    public int hashCode() {
//        return Objects.hash(x, y);
//    }
//
//    @Override
//    public String toString() {
//        return "Step{" +
//                "x=" + x +
//                ", y=" + y +
//                ", cost=" + cost +
//                '}';
//    }
//
//    public int getX() {
//        return x;
//    }
//
//    public void setX(int x) {
//        this.x = x;
//    }
//
//    public int getY() {
//        return y;
//    }
//
//    public void setY(int y) {
//        this.y = y;
//    }
//
//    public int getCost() {
//        return cost;
//    }
//
//    public void setCost(int cost) {
//        this.cost = cost;
//    }
//}
